10494. Если бы мы снова стали детьми

Необходимо найти частное или остаток от деления длинного целого числа на короткое целое.

Вход. Каждая строка содержит два числа, разделенных знаком ‘/’ (целочисленное деление) или ‘%’ (остаток от деления). Между числами и знаком операции может находиться произвольное число пробелов. Первое число m является длинным целым. Второе целое n лежит в промежутке 0 < n < 2³¹.

Выход. Для каждого теста вывести значение m / n или m % n в зависимости от операции.

Пример входа

110 / 100

99 % 10

2147483647 / 2147483647

2147483646 % 2147483647

Пример выхода

1

9

1

2147483646

РЕШЕНИЕ

вычисления

Анализ алгоритма

Техническая задача. Необходимо реализовать деление длинного целого числа на короткое целое. Будем реализовывать деление в столбик. Пусть следует разделить число a₁a₂…a_k на n. Пусть r₁r₂…r_l – полученное частное. Положим вначале текущий остаток ost равным нулю. Снос очередной цифры делимого эквивалентен умножению текущего остатка на 10 и прибавления к нему этой цифры. То есть после сноса цифры a_i получим 10 * ost + a_i. Частным от деления этого числа на 10 будет очередная цифра частного r_i, а остатком от его деления на 10 будет новый остаток. Эту операцию следует провести для всех цифр делимого, то есть k раз. В частном получим r₁ = … = r_t = 0, где t – максимальный номер цифры, для которой a₁…a_t < n (то есть при делении на n чисел a₁, a₁a₂, a₁…a_t в частном получается ноль). Таким образом, в случае вывода частного следует пропустить ведущие нули.

Реализация алгоритма

В массиве m будем хранить делимое, в res – частное. Делитель n следует объявить как 64-битовое целое, иначе в дальнейших вычислениях будет иметь место переполнение. В переменной ost будем хранить остаток от деления m на n.

int m[1000],res[1000];

long long n,ost;

Пока не конец файла для каждого теста посимвольно читаем первое число (делимое) в массив m. Пропускаем пробелы, после чего в переменной c будет находиться знак операции. Читаем второе число в переменную n. Следует вместе с переменной n прочитать символ перехода на новую строку ‘\n’ (иначе при посимвольном чтении делимого со следующего теста первым прочитанным символом будет ‘\n’, а не первая цифра числа).

while (!feof(stdin))

{

k=0;

while(isdigit(c = getchar())) m[k++] = c - '0';

while((c = getchar()) == ' ');

scanf("%d\n",&n);

Положим остаток ost равным нулю. Совершаем деление m на n в столбик.

ost = 0;

for(i=0;i<k;i++)

{

res[i] = (int)((ost*10 + m[i]) / n);

ost = (ost*10 + m[i]) % n;

}

Если в тесте следует выполнить операцию взятия остатка, то выводим значение переменной ost. Иначе выводим частное, которое хранится в массиве res. При выводе частного необходимо пропустить ведущие нули. Отдельно следует обработать случай, когда частное равно нулю.

if (c == '%') printf("%lld\n",ost);

else

{

i=0; while((res[i]==0) && (i < k)) i++;

if (i < k) for(;i<k;i++) printf("%d",res[i]);

else printf("0");

printf("\n");

}

}